#include <iostream>
#include <vector>
// void count_sort(std::vector<int> &v) {
//   // 找到数组中最大元素
//   if (v.size() < 2) {
//     return;
//   }
//   int max = v[0];
//   for (const int &i : v) {
//     if (i > max) {
//       max = i;
//     }
//   }
//   std::vector<int> counter(max + 1);
//   // 计数
//   for (const int &i : v) {
//     counter[i]++;
//   }
//   // 输出排序结果
//   int n = 0;
//   for (int i = 0; i < counter.size(); i++) {
//     if (counter[i] > 0) {
//       for (int j = 0; j < counter[i]; j++) {
//         v[n++] = i;
//       }
//     }
//   }
// }

void count_sort(std::vector<int> &v) {
  // 找到数组中最大元素
  if (v.size() < 2) {
    return;
  }
  int max = v[0];
  for (const int &i : v) {
    if (i > max) {
      max = i;
    }
  }
  std::vector<int> counter(max + 1);
  // 计数
  for (const int &i : v) {
    counter[i]++;
  }
  // 计算前缀和
  std::vector<int> prefix(max + 1);
  prefix[0] = counter[0];
  for (int i = 1; i < counter.size(); i++) {
    prefix[i] = prefix[i - 1] + counter[i];
  }
  // 反向遍历数组
  std::vector<int> res(v.size());
  for (int i = v.size() - 1; i >= 0; i--) {
    int num = v[i];
    int pos = prefix[num] - 1;
    res[pos] = num;
  }
  // 输出排序结果
  for (int i = 0; i < res.size(); i++) {
    v[i] = res[i];
  }
}

int main() {
  std::vector<int> list = {9, 8, 6, 4, 5, 3, 1, 2};
  count_sort(list);
  for (int &i : list) {
    std::cout << i;
  }

  return 0;
}